<!DOCTYPE html>
<html dir="ltr" lang="zh">
<head>
<meta charset="utf-8"/>
<meta content="width=device-width, initial-scale=1.0" name="viewport"/>
<meta content="HashMap 相关学习总结 # 相关问题 # 红黑树相关问题 # 关于底层数据结构，HashMap 的 JDK 1.7 和 JDK 1.8 有何不同？ # 点击展开 ... JDK 1.7 组成：数组 + 链表 JDK 1.8 组成：数组 + 链表/红黑树 为什么要用红黑树？ # 点击展开 ... 红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况。 为何不一上来就树化？ # 点击展开 ... 刚刚开始时，链表长度都比较短，这时候链表的效率并不一定比树化后低，并且树化还会浪费存储。
其次，hash 表的查找、更新的时间复杂度是 O(1) ，而红黑树的查找、更新的时间复杂度是 O(log2 n)，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表。
树化阈值为何为 8？ # 点击展开 ... 主要是为在时间和空间上恰好达到平衡，8 是根据概率统计而寻找的值。
hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过8的链表出现概率是
0.00000006（亿分之六），选择 8 就是为了让树化机率足够小。
是不是一超过阈值就立马变为红黑树？是否要满足一些其他条件？ # 点击展开 ... 不是。" name="description"/>
<meta content="#FFFFFF" name="theme-color"/>
<meta content="light dark" name="color-scheme"/><meta content="" property="og:title"/>
<meta content="HashMap 相关学习总结 # 相关问题 # 红黑树相关问题 # 关于底层数据结构，HashMap 的 JDK 1.7 和 JDK 1.8 有何不同？ # 点击展开 ... JDK 1.7 组成：数组 + 链表 JDK 1.8 组成：数组 + 链表/红黑树 为什么要用红黑树？ # 点击展开 ... 红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况。 为何不一上来就树化？ # 点击展开 ... 刚刚开始时，链表长度都比较短，这时候链表的效率并不一定比树化后低，并且树化还会浪费存储。
其次，hash 表的查找、更新的时间复杂度是 O(1) ，而红黑树的查找、更新的时间复杂度是 O(log2 n)，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表。
树化阈值为何为 8？ # 点击展开 ... 主要是为在时间和空间上恰好达到平衡，8 是根据概率统计而寻找的值。
hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过8的链表出现概率是
0.00000006（亿分之六），选择 8 就是为了让树化机率足够小。
是不是一超过阈值就立马变为红黑树？是否要满足一些其他条件？ # 点击展开 ... 不是。" property="og:description"/>
<meta content="article" property="og:type"/>
<meta content="https://helloputong.gitee.io/notes/java/hashmap-%E7%9B%B8%E5%85%B3%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/" property="og:url"/><meta content="notes" property="article:section"/>
<title>Hash Map 相关学习总结 | Hello! 噗通 🍀</title>
<link href="/manifest.json" rel="manifest"/>
<link href="/favicon.png" rel="icon" type="image/x-icon"/>
<link crossorigin="anonymous" href="/book.min.a82d7e77ceb134d151c4d7e381eeb30623fbd5a524d58c584d8716ecec0205bd.css" integrity="sha256-qC1+d86xNNFRxNfjge6zBiP71aUk1YxYTYcW7OwCBb0=" rel="stylesheet"/>
<script defer="" src="/flexsearch.min.js"></script>
<script crossorigin="anonymous" defer="" integrity="sha256-+pR/j4Voa/VXQmH38FekcfPx1IEWD5WAkNOJruKNmQk=" src="/zh.search.min.fa947f8f85686bf5574261f7f057a471f3f1d481160f958090d389aee28d9909.js"></script>
<script crossorigin="anonymous" defer="" integrity="sha256-b2+Q/LjrHEnsOJg45rgB0N4ZQwuOUWkC+NdcPIvZhzk=" src="/sw.min.6f6f90fcb8eb1c49ec389838e6b801d0de19430b8e516902f8d75c3c8bd98739.js"></script>
<!--
Made with Book Theme
https://github.com/alex-shpak/hugo-book
-->
</head>
<body dir="ltr">
<input class="hidden toggle" id="menu-control" type="checkbox"/>
<input class="hidden toggle" id="toc-control" type="checkbox"/>
<main class="container flex">
<aside class="book-menu">
<div class="book-menu-content">
<nav>
<h2 class="book-brand">
<a class="flex align-center" href="/"><span>Hello! 噗通 🍀</span>
</a>
</h2>
<div class="book-search">
<input aria-label="Search" data-hotkeys="s/" id="book-search-input" maxlength="64" placeholder="Search" type="text"/>
<div class="book-search-spinner hidden"></div>
<ul id="book-search-results"></ul>
</div>
<ul>
<li class="book-section-flat">
<span>--学习笔记--👇</span>
<ul>
<li>
<input class="toggle" id="section-62161c8b7eae8ea89aee3d6f310b2312" type="checkbox"/>
<label class="flex justify-between" for="section-62161c8b7eae8ea89aee3d6f310b2312">
<a class="" role="button">Android</a>
</label>
<ul>
<li>
<a class="" href="/notes/android/mac%E9%80%9A%E8%BF%87homebrew%E5%AE%89%E8%A3%85java8/">Mac 通过 Homebrew 安装 Java8</a>
</li>
<li>
<a class="" href="/notes/android/%E6%B4%BB%E5%8A%A8%E7%9A%84%E7%94%9F%E5%91%BD%E5%91%A8%E6%9C%9F/">活动的生命周期</a>
</li>
<li>
<a class="" href="/notes/android/%E5%B8%B8%E7%94%A8%E6%8E%A7%E4%BB%B6%E5%92%8C4%E7%A7%8D%E5%B8%83%E5%B1%80/">常用控件和4种布局</a>
</li>
<li>
<a class="" href="/notes/android/android-%E4%B8%AD%E4%BA%8B%E4%BB%B6%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/">Android 中事件学习总结</a>
</li>
<li>
<a class="" href="/notes/android/android-%E4%B8%AD%E7%9A%84%E6%B6%88%E6%81%AF%E6%9C%BA%E5%88%B6%E5%92%8C%E5%BC%82%E6%AD%A5%E4%BB%BB%E5%8A%A1/">Android 中的消息机制和异步任务</a>
</li>
<li>
<a class="" href="/notes/android/listview%E4%B8%AD%E5%85%B3%E4%BA%8E%E6%95%B0%E6%8D%AE%E6%9B%B4%E6%96%B0%E7%9A%84%E4%B8%A4%E4%B8%AA%E9%97%AE%E9%A2%98/">List View中关于数据更新的两个问题</a>
</li>
<li>
<a class="" href="/notes/android/spinner-%E5%9F%BA%E6%9C%AC%E4%BD%BF%E7%94%A8/">Spinner 基本使用</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-d1dc8d9746f5c776e8a82499bbb2e7c6" type="checkbox"/>
<label class="flex justify-between" for="section-d1dc8d9746f5c776e8a82499bbb2e7c6">
<a class="" role="button">BMS</a>
</label>
<ul>
<li>
<a class="" href="/notes/bms/bms-%E7%9B%B8%E5%85%B3%E7%90%86%E8%AE%BA%E5%AD%A6%E4%B9%A0/">BMS 相关概念</a>
</li>
<li>
<a class="" href="/notes/bms/%E6%BC%94%E7%A4%BA%E5%8F%82%E6%95%B0%E8%A7%A3%E8%AF%BB/">功能演示</a>
</li>
<li>
<a class="" href="/notes/bms/%E5%8E%9F%E7%90%86%E5%9B%BE%E8%A7%A3%E8%AF%BB/">原理图解读</a>
</li>
<li>
<a class="" href="/notes/bms/%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90/">源码解析</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-b7444509cb631180897a34f028407c2c" type="checkbox"/>
<label class="flex justify-between" for="section-b7444509cb631180897a34f028407c2c">
<a class="" role="button">设计模式</a>
</label>
<ul>
<li>
<a class="" href="/notes/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/uml-%E5%9B%BE/">Uml 图</a>
</li>
<li>
<a class="" href="/notes/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E8%AE%BE%E8%AE%A1%E5%8E%9F%E5%88%99/">设计原则</a>
</li>
<li>
<a class="" href="/notes/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E5%88%9B%E5%BB%BA%E5%9E%8B%E6%A8%A1%E5%BC%8F/">创建型模式</a>
</li>
<li>
<a class="" href="/notes/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E7%BB%93%E6%9E%84%E5%9E%8B%E6%A8%A1%E5%BC%8F/">结构型模式</a>
</li>
<li>
<a class="" href="/notes/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E8%A1%8C%E4%B8%BA%E5%9E%8B%E6%A8%A1%E5%BC%8F/">行为型模式</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-4364152b7ab5995d509c0b7b811005c4" type="checkbox"/>
<label class="flex justify-between" for="section-4364152b7ab5995d509c0b7b811005c4">
<a class="" role="button">JVM</a>
</label>
<ul>
<li>
<a class="" href="/notes/jvm/%E4%BB%80%E4%B9%88%E6%98%AF-jvm/">什么是 Jvm</a>
</li>
<li>
<a class="" href="/notes/jvm/%E7%A8%8B%E5%BA%8F%E8%AE%A1%E6%95%B0%E5%99%A8/">程序计数器</a>
</li>
<li>
<a class="" href="/notes/jvm/%E8%99%9A%E6%8B%9F%E6%9C%BA%E6%A0%88/">虚拟机栈</a>
</li>
<li>
<a class="" href="/notes/jvm/%E6%9C%AC%E5%9C%B0%E6%96%B9%E6%B3%95%E6%A0%88-/">本地方法栈</a>
</li>
<li>
<a class="" href="/notes/jvm/%E5%A0%86/">堆</a>
</li>
<li>
<a class="" href="/notes/jvm/%E6%96%B9%E6%B3%95%E5%8C%BA/">方法区</a>
</li>
<li>
<a class="" href="/notes/jvm/%E7%9B%B4%E6%8E%A5%E5%86%85%E5%AD%98/">直接内存</a>
</li>
<li>
<a class="" href="/notes/jvm/%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6/">垃圾回收</a>
</li>
<li>
<a class="" href="/notes/jvm/%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6%E5%99%A8/">垃圾回收器</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-61661238f18c0095524962a5d1d6e676" type="checkbox"/>
<label class="flex justify-between" for="section-61661238f18c0095524962a5d1d6e676">
<a class="" role="button">Spring</a>
</label>
<ul>
<li>
<a class="" href="/notes/spring/beanfactory%E4%B8%8Eapplicationcontext/">Bean Factory与 Application Context</a>
</li>
<li>
<a class="" href="/notes/spring/nacos-%E9%85%8D%E7%BD%AE%E4%B8%AD%E5%BF%83/">Nacos 配置中心</a>
</li>
<li>
<a class="" href="/notes/spring/open-feign-%E8%BF%9C%E7%A8%8B%E8%B0%83%E7%94%A8%E7%A4%BA%E4%BE%8B/">Open Feign 远程调用示例</a>
</li>
<li>
<a class="" href="/notes/spring/springboot-%E6%95%B4%E5%90%88-mybatis-plus/">Spring Boot 整合 My Batis Plus</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-39abd0d44427d4a54e694a2b3f22d967" type="checkbox"/>
<label class="flex justify-between" for="section-39abd0d44427d4a54e694a2b3f22d967">
<a class="" role="button">TensorFlow</a>
</label>
<ul>
<li>
<a class="" href="/notes/tensorflow/tensorflow-%E7%AC%94%E8%AE%B0%E4%B8%80/">Tensor Flow 笔记（一）</a>
</li>
<li>
<a class="" href="/notes/tensorflow/tensorflow-%E7%AC%94%E8%AE%B0%E4%BA%8C/">Tensor Flow 笔记（二）</a>
</li>
<li>
<a class="" href="/notes/tensorflow/tensorflow-%E7%AC%94%E8%AE%B0%E4%B8%89/">Tensor Flow 笔记（三）</a>
</li>
<li>
<a class="" href="/notes/tensorflow/tensorflow-%E7%AC%94%E8%AE%B0%E5%9B%9B/">Tensor Flow 笔记（四）</a>
</li>
<li>
<a class="" href="/notes/tensorflow/tensorflow-%E7%AC%94%E8%AE%B0%E4%BA%94/">Tensor Flow 笔记（五）</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-e2ca0d138d67d9d3ae55da25ac044829" type="checkbox"/>
<label class="flex justify-between" for="section-e2ca0d138d67d9d3ae55da25ac044829">
<a class="" role="button">Redis</a>
</label>
<ul>
<li>
<a class="" href="/notes/redis/nosql%E6%95%B0%E6%8D%AE%E5%BA%93%E7%AE%80%E4%BB%8B/">No Sql数据库简介</a>
</li>
<li>
<a class="" href="/notes/redis/redis-key/">Redis Key</a>
</li>
<li>
<a class="" href="/notes/redis/redis-string/">Redis String</a>
</li>
<li>
<a class="" href="/notes/redis/redis-list/">Redis List</a>
</li>
<li>
<a class="" href="/notes/redis/redis-set/">Redis Set</a>
</li>
<li>
<a class="" href="/notes/redis/redis-hash/">Redis Hash</a>
</li>
<li>
<a class="" href="/notes/redis/redis-zset/">Redis Zset</a>
</li>
<li>
<a class="" href="/notes/redis/redis-%E5%8F%91%E5%B8%83%E4%B8%8E%E8%AE%A2%E9%98%85/">Redis 发布与订阅</a>
</li>
<li>
<a class="" href="/notes/redis/redis-jedis/">Redis Jedis</a>
</li>
<li>
<a class="" href="/notes/redis/springboot-%E6%95%B4%E5%90%88-redis/">Spring Boot 整合 Redis</a>
</li>
<li>
<a class="" href="/notes/redis/redis-%E4%BA%8B%E5%8A%A1%E5%92%8C%E9%94%81%E6%9C%BA%E5%88%B6/">Redis 事务和锁机制</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-58f730a0b22fcdc7a886db614d77f88c" type="checkbox"/>
<label class="flex justify-between" for="section-58f730a0b22fcdc7a886db614d77f88c">
<a class="" role="button">代码随想录刷题</a>
</label>
<ul>
<li>
<a class="" href="/notes/leetcode/day001-%E7%AC%AC%E4%B8%80%E7%AB%A0%E6%95%B0%E7%BB%84/">Day001 第一章数组</a>
</li>
<li>
<a class="" href="/notes/leetcode/day002-%E7%AC%AC%E4%B8%80%E7%AB%A0%E6%95%B0%E7%BB%84/">Day002 第一章数组</a>
</li>
<li>
<a class="" href="/notes/leetcode/day003-%E7%AC%AC%E4%BA%8C%E7%AB%A0%E9%93%BE%E8%A1%A8/">Day003 第二章链表</a>
</li>
<li>
<a class="" href="/notes/leetcode/day004-%E7%AC%AC%E4%BA%8C%E7%AB%A0%E9%93%BE%E8%A1%A8/">Day004 第二章链表</a>
</li>
<li>
<a class="" href="/notes/leetcode/day006-%E7%AC%AC%E4%B8%89%E7%AB%A0%E5%93%88%E5%B8%8C%E8%A1%A8/">Day006 第三章哈希表</a>
</li>
<li>
<a class="" href="/notes/leetcode/day007-%E7%AC%AC%E4%B8%89%E7%AB%A0%E5%93%88%E5%B8%8C%E8%A1%A8/">Day007 第三章哈希表</a>
</li>
<li>
<a class="" href="/notes/leetcode/day008-%E7%AC%AC%E5%9B%9B%E7%AB%A0%E5%AD%97%E7%AC%A6%E4%B8%B2/">Day008 第四章字符串</a>
</li>
<li>
<a class="" href="/notes/leetcode/day009-%E7%AC%AC%E5%9B%9B%E7%AB%A0%E5%AD%97%E7%AC%A6%E4%B8%B2/">Day009 第四章字符串</a>
</li>
<li>
<a class="" href="/notes/leetcode/day010-%E7%AC%AC%E4%BA%94%E7%AB%A0%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/">Day010 第五章栈与队列</a>
</li>
<li>
<a class="" href="/notes/leetcode/day011-%E7%AC%AC%E4%BA%94%E7%AB%A0%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/">Day011 第五章栈与队列</a>
</li>
<li>
<a class="" href="/notes/leetcode/day013-%E7%AC%AC%E4%BA%94%E7%AB%A0%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/">Day013 第五章栈与队列</a>
</li>
<li>
<a class="" href="/notes/leetcode/day014-%E7%AC%AC%E5%85%AD%E7%AB%A0%E4%BA%8C%E5%8F%89%E6%A0%91/">Day014 第六章二叉树</a>
</li>
<li>
<a class="" href="/notes/leetcode/day015-%E7%AC%AC%E5%85%AD%E7%AB%A0%E4%BA%8C%E5%8F%89%E6%A0%91/">Day015 第六章二叉树</a>
</li>
<li>
<a class="" href="/notes/leetcode/day017-%E7%AC%AC%E5%85%AD%E7%AB%A0%E4%BA%8C%E5%8F%89%E6%A0%91/">Day017 第六章二叉树</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-4f95435d3a74007e2c985ea455bbb6e6" type="checkbox"/>
<label class="flex justify-between" for="section-4f95435d3a74007e2c985ea455bbb6e6">
<a class="" role="button">MyBatisPlus</a>
</label>
<ul>
<li>
<a class="" href="/notes/mybatisplus/%E5%BF%AB%E9%80%9F%E5%85%A5%E9%97%A8/">MP快速入门</a>
</li>
<li>
<a class="" href="/notes/mybatisplus/%E4%B8%80%E8%88%AC%E6%9F%A5%E8%AF%A2%E6%93%8D%E4%BD%9C/">一般查询操作</a>
</li>
<li>
<a class="" href="/notes/mybatisplus/%E5%88%86%E9%A1%B5%E6%9F%A5%E8%AF%A2/">分页查询</a>
</li>
<li>
<a class="" href="/notes/mybatisplus/%E9%80%BB%E8%BE%91%E5%88%A0%E9%99%A4/">逻辑删除</a>
</li>
<li>
<a class="" href="/notes/mybatisplus/%E6%9D%A1%E4%BB%B6%E6%9F%A5%E8%AF%A2/">条件查询</a>
</li>
<li>
<a class="" href="/notes/mybatisplus/%E5%B0%81%E8%A3%85service%E4%BD%BF%E7%94%A8/">封装service使用</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-3907b2cf55ed520ad784e24525c8baa4" type="checkbox"/>
<label class="flex justify-between" for="section-3907b2cf55ed520ad784e24525c8baa4">
<a class="" role="button">Swift</a>
</label>
<ul>
<li>
<a class="" href="/notes/swift/swiftui-%E5%B8%B8%E7%94%A8%E8%A7%86%E5%9B%BE-views/">Swift Ui 常用视图 Views</a>
</li>
<li>
<a class="" href="/notes/swift/swiftui-%E4%BF%A1%E6%81%AF%E8%A7%86%E5%9B%BE-views/">Swift Ui 信息视图 Views</a>
</li>
<li>
<a class="" href="/notes/swift/swiftui-%E5%B1%82%E7%BA%A7%E8%A7%86%E5%9B%BE-views/">Swift Ui 层级视图 Views</a>
</li>
<li>
<a class="" href="/notes/swift/swiftui-%E6%8E%A7%E5%88%B6%E8%A7%86%E5%9B%BE-views/">Swift Ui 控制视图 Views</a>
</li>
</ul>
</li>
<li>
<input checked="" class="toggle" id="section-0f70934a6e5284fbc93928c61dfe9c83" type="checkbox"/>
<label class="flex justify-between" for="section-0f70934a6e5284fbc93928c61dfe9c83">
<a class="" role="button">Java</a>
</label>
<ul>
<li>
<a class="" href="/notes/java/arraylist-%E6%89%A9%E5%AE%B9%E8%A7%84%E5%88%99/">Array List 扩容规则</a>
</li>
<li>
<a class="active" href="/notes/java/hashmap-%E7%9B%B8%E5%85%B3%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/">Hash Map 相关学习总结</a>
</li>
<li>
<a class="" href="/notes/java/java-%E5%8F%8D%E5%B0%84/">Java 反射</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-3d1ea9814960db7e996773b67773e705" type="checkbox"/>
<label class="flex justify-between" for="section-3d1ea9814960db7e996773b67773e705">
<a class="" role="button">Java八股</a>
</label>
<ul>
<li>
<a class="" href="/notes/java-%E7%9B%B8%E5%85%B3/%E5%B9%B6%E5%8F%91/">Concurrence</a>
</li>
<li>
<a class="" href="/notes/java-%E7%9B%B8%E5%85%B3/mybatis/">MyBatis</a>
</li>
<li>
<a class="" href="/notes/java-%E7%9B%B8%E5%85%B3/mysql/">MySQL</a>
</li>
<li>
<a class="" href="/notes/java-%E7%9B%B8%E5%85%B3/jvm/">Jvm</a>
</li>
<li>
<a class="" href="/notes/java-%E7%9B%B8%E5%85%B3/redis/">Redis</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-ea55243c547fa272027885b73a74852e" type="checkbox"/>
<label class="flex justify-between" for="section-ea55243c547fa272027885b73a74852e">
<a class="" role="button">嵌入式重点总结</a>
</label>
<ul>
<li>
<a class="" href="/notes/%E5%B5%8C%E5%85%A5%E5%BC%8F%E6%80%BB%E7%BB%93/c/">C 语言相关</a>
</li>
<li>
<a class="" href="/notes/%E5%B5%8C%E5%85%A5%E5%BC%8F%E6%80%BB%E7%BB%93/%E4%B8%AD%E6%96%AD%E7%B3%BB%E7%BB%9F/">中断系统</a>
</li>
<li>
<a class="" href="/notes/%E5%B5%8C%E5%85%A5%E5%BC%8F%E6%80%BB%E7%BB%93/%E5%AE%9A%E6%97%B6%E5%99%A8/">TIM</a>
</li>
<li>
<a class="" href="/notes/%E5%B5%8C%E5%85%A5%E5%BC%8F%E6%80%BB%E7%BB%93/adc/">ADC</a>
</li>
<li>
<a class="" href="/notes/%E5%B5%8C%E5%85%A5%E5%BC%8F%E6%80%BB%E7%BB%93/%E5%B8%B8%E8%A7%81%E9%97%AE%E9%A2%98/">嵌入式知识点串烧</a>
</li>
</ul>
</li>
</ul>
</li>
<li class="book-section-flat">
<span>--解决方案--👇</span>
<ul>
<li>
<input class="toggle" id="section-f1d4602254471b9d0da445dd468cd456" type="checkbox"/>
<label class="flex justify-between" for="section-f1d4602254471b9d0da445dd468cd456">
<a class="" role="button">环境配置</a>
</label>
<ul>
<li>
<a class="" href="/solution/environment/apple-m%E7%B3%BB%E5%88%97%E8%8A%AF%E7%89%87%E5%AE%89%E8%A3%85-pyqt/">Apple M系列芯片安装 Pyqt</a>
</li>
<li>
<a class="" href="/solution/environment/docker-%E5%AE%89%E8%A3%85-redis-/">Docker 安装 Redis</a>
</li>
<li>
<a class="" href="/solution/environment/hugo-%E4%B8%BB%E9%A2%98-hugo-book-%E4%B8%AD%E8%8B%B1%E6%96%87%E6%90%9C%E7%B4%A2%E9%85%8D%E7%BD%AE/">Hugo 主题 Hugo Book 中英文搜索配置</a>
</li>
<li>
<a class="" href="/solution/environment/iterm2-oh-my-zsh-%E9%85%8D%E7%BD%AE/">I Term2 Oh My Zsh 配置</a>
</li>
<li>
<a class="" href="/solution/environment/m1-%E8%8A%AF%E7%89%87-docker-%E5%AE%89%E8%A3%85-mysql5.7-/">M1 芯片 Docker 安装 Mysql5.7</a>
</li>
<li>
<a class="" href="/solution/environment/mac-idea-%E5%BF%AB%E6%8D%B7%E9%94%AE%E4%BD%8D/">MAC Idea 快捷键位</a>
</li>
<li>
<a class="" href="/solution/environment/mac-%E5%90%AF%E5%8A%A8%E5%8F%B0%E8%87%AA%E5%AE%9A%E4%B9%89%E8%A1%8C%E5%88%97%E5%B8%83%E5%B1%80/">MAC 启动台自定义行列布局</a>
</li>
<li>
<a class="" href="/solution/environment/%E5%86%85%E7%BD%91%E7%A9%BF%E9%80%8F/">内网穿透</a>
</li>
<li>
<a class="" href="/solution/environment/%E5%86%85%E7%BD%91%E7%A9%BF%E9%80%8F%E7%9A%84%E8%87%AA%E5%90%AF%E5%8A%A8%E8%AE%BE%E7%BD%AE/">内网穿透的自启动设置</a>
</li>
</ul>
</li>
<li>
<input class="toggle" id="section-5a76a664ba4855b79d3c1bc77e5b08b1" type="checkbox"/>
<label class="flex justify-between" for="section-5a76a664ba4855b79d3c1bc77e5b08b1">
<a class="" role="button">杂乱问题</a>
</label>
<ul>
<li>
<a class="" href="/solution/problems/brew-%E4%B8%80%E4%BA%9B%E5%B8%B8%E7%94%A8%E5%91%BD%E4%BB%A4/">Brew 一些常用命令</a>
</li>
<li>
<a class="" href="/solution/problems/docker-%E5%B8%B8%E7%94%A8%E5%91%BD%E4%BB%A4/">Docker 常用命令</a>
</li>
<li>
<a class="" href="/solution/problems/git-github-%E7%9B%B8%E5%85%B3%E5%91%BD%E4%BB%A4%E6%95%B4%E7%90%86/">Git Git Hub 相关命令整理</a>
</li>
<li>
<a class="" href="/solution/problems/%E9%9D%A2%E8%AF%95%E9%A2%98%E6%89%AB%E7%9B%B2/">面试题扫盲</a>
</li>
</ul>
</li>
</ul>
</li>
<li class="book-section-flat">
<span>一点业余👇</span>
<ul>
</ul>
</li>
<li class="book-section-flat">
<span>--其他记录--👇</span>
<ul>
<li>
<input class="toggle" id="section-9ef4d2063ddc9af7785b193647f22260" type="checkbox"/>
<label class="flex justify-between" for="section-9ef4d2063ddc9af7785b193647f22260">
<a class="" role="button">我和阿刁</a>
</label>
<ul>
<li>
<a class="" href="/daily/ad/%E5%85%B3%E4%BA%8E%E9%98%BF%E5%88%812022%E5%B9%B4%E7%9A%84%E7%94%9F%E6%97%A5%E7%9A%84%E5%B0%8F%E8%AE%BA%E6%96%87/">关于阿刁2022年的生日的小论文</a>
</li>
<li>
<a class="" href="/daily/ad/%E5%85%B3%E4%BA%8E%E9%98%BF%E5%88%81%E7%9A%842021%E5%B9%B4%E5%BA%A6%E6%80%BB%E7%BB%93/">关于阿刁的2021年度总结</a>
</li>
<li>
<a class="" href="/daily/ad/%E5%85%B3%E4%BA%8E%E9%98%BF%E5%88%81%E7%9A%842022%E5%B9%B4%E5%BA%A6%E6%80%BB%E7%BB%93/">关于阿刁的2022年度总结</a>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</nav>
<script>(function(){var e=document.querySelector("aside .book-menu-content");addEventListener("beforeunload",function(){localStorage.setItem("menu.scrollTop",e.scrollTop)}),e.scrollTop=localStorage.getItem("menu.scrollTop")})()</script>
</div>
</aside>
<div class="book-page">
<header class="book-header">
<div class="flex align-center justify-between">
<label for="menu-control">
<img alt="Menu" class="book-icon" src="/svg/menu.svg"/>
</label>
<strong>Hash Map 相关学习总结</strong>
<label for="toc-control">
<img alt="Table of Contents" class="book-icon" src="/svg/toc.svg"/>
</label>
</div>
<aside class="hidden clearfix">
<nav id="TableOfContents">
<ul>
<li><a href="#hashmap-相关学习总结">HashMap 相关学习总结</a>
<ul>
<li><a href="#相关问题">相关问题</a>
<ul>
<li><a href="#红黑树相关问题">红黑树相关问题</a>
<ul>
<li><a href="#关于底层数据结构hashmap-的-jdk-17-和-jdk-18-有何不同">关于底层数据结构，HashMap 的 JDK 1.7 和 JDK 1.8 有何不同？</a></li>
<li><a href="#为什么要用红黑树">为什么要用红黑树？</a></li>
<li><a href="#为何不一上来就树化">为何不一上来就树化？</a></li>
<li><a href="#树化阈值为何为-8">树化阈值为何为 8？</a></li>
<li><a href="#是不是一超过阈值就立马变为红黑树是否要满足一些其他条件">是不是一超过阈值就立马变为红黑树？是否要满足一些其他条件？</a></li>
<li><a href="#红黑树什么时候会退化成链表">红黑树什么时候会退化成链表？</a></li>
</ul>
</li>
<li><a href="#索引相关问题">索引相关问题</a>
<ul>
<li><a href="#索引计算方法">索引计算方法？</a></li>
<li><a href="#hashcode-都有了为何还要提供-hash-方法"><code>hashCode</code> 都有了，为何还要提供 <code>hash()</code> 方法？</a></li>
<li><a href="#数组容量为何是-2-的-n-次幂">数组容量为何是 2 的 n 次幂？</a></li>
</ul>
</li>
<li><a href="#put-与-扩容-相关问题">put 与 扩容 相关问题</a>
<ul>
<li><a href="#put-流程">put 流程？</a></li>
<li><a href="#扩容加载因子为何默认是-075f-">扩容（加载）因子为何默认是 0.75f ？</a></li>
</ul>
</li>
<li><a href="#并发问题">并发问题</a>
<ul>
<li><a href="#多线程下操作-hashmap-会有什么问题">多线程下操作 HashMap 会有什么问题？</a></li>
<li><a href="#key-的设计要求-">key 的设计要求 ？</a></li>
</ul>
</li>
<li><a href="#key-相关问题">key 相关问题</a>
<ul>
<li><a href="#string-对象的-hashcode-设计">String 对象的 <code>hashCode()</code> 设计?</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</nav>
</aside>
</header>
<article class="markdown"><h1 id="hashmap-相关学习总结">
  HashMap 相关学习总结
  <a class="anchor" href="#hashmap-%e7%9b%b8%e5%85%b3%e5%ad%a6%e4%b9%a0%e6%80%bb%e7%bb%93">#</a>
</h1>
<h2 id="相关问题">
  相关问题
  <a class="anchor" href="#%e7%9b%b8%e5%85%b3%e9%97%ae%e9%a2%98">#</a>
</h2>
<h3 id="红黑树相关问题">
  红黑树相关问题
  <a class="anchor" href="#%e7%ba%a2%e9%bb%91%e6%a0%91%e7%9b%b8%e5%85%b3%e9%97%ae%e9%a2%98">#</a>
</h3>
<h4 id="关于底层数据结构hashmap-的-jdk-17-和-jdk-18-有何不同">
  关于底层数据结构，HashMap 的 JDK 1.7 和 JDK 1.8 有何不同？
  <a class="anchor" href="#%e5%85%b3%e4%ba%8e%e5%ba%95%e5%b1%82%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84hashmap-%e7%9a%84-jdk-17-%e5%92%8c-jdk-18-%e6%9c%89%e4%bd%95%e4%b8%8d%e5%90%8c">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<ul>
<li>JDK 1.7 组成：数组 + 链表</li>
<li>JDK 1.8 组成：数组 + 链表/红黑树</li>
</ul>
</div>
</label>
</div>
<h4 id="为什么要用红黑树">
  为什么要用红黑树？
  <a class="anchor" href="#%e4%b8%ba%e4%bb%80%e4%b9%88%e8%a6%81%e7%94%a8%e7%ba%a2%e9%bb%91%e6%a0%91">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
      红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况。
    </div>
</label>
</div>
<h4 id="为何不一上来就树化">
  为何不一上来就树化？
  <a class="anchor" href="#%e4%b8%ba%e4%bd%95%e4%b8%8d%e4%b8%80%e4%b8%8a%e6%9d%a5%e5%b0%b1%e6%a0%91%e5%8c%96">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<p>刚刚开始时，链表长度都比较短，这时候链表的效率并不一定比树化后低，并且树化还会浪费存储。</p>
<p>其次，hash 表的查找、更新的时间复杂度是 O(1) ，而红黑树的查找、更新的时间复杂度是 O(log2 n)，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表。</p>
</div>
</label>
</div>
<h4 id="树化阈值为何为-8">
  树化阈值为何为 8？
  <a class="anchor" href="#%e6%a0%91%e5%8c%96%e9%98%88%e5%80%bc%e4%b8%ba%e4%bd%95%e4%b8%ba-8">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<p>主要是为在时间和空间上恰好达到平衡，8 是根据概率统计而寻找的值。</p>
<p>hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过8的链表出现概率是</p>
<p>0.00000006（亿分之六），选择 8 就是为了让树化机率足够小。</p>
</div>
</label>
</div>
<h4 id="是不是一超过阈值就立马变为红黑树是否要满足一些其他条件">
  是不是一超过阈值就立马变为红黑树？是否要满足一些其他条件？
  <a class="anchor" href="#%e6%98%af%e4%b8%8d%e6%98%af%e4%b8%80%e8%b6%85%e8%bf%87%e9%98%88%e5%80%bc%e5%b0%b1%e7%ab%8b%e9%a9%ac%e5%8f%98%e4%b8%ba%e7%ba%a2%e9%bb%91%e6%a0%91%e6%98%af%e5%90%a6%e8%a6%81%e6%bb%a1%e8%b6%b3%e4%b8%80%e4%ba%9b%e5%85%b6%e4%bb%96%e6%9d%a1%e4%bb%b6">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<p>不是。</p>
<p>需要同时满足以下条件</p>
<ul>
<li>数组容量<strong>大于等于</strong>64</li>
<li>链表长度<strong>大于</strong>8</li>
</ul>
</div>
</label>
</div>
<h4 id="红黑树什么时候会退化成链表">
  红黑树什么时候会退化成链表？
  <a class="anchor" href="#%e7%ba%a2%e9%bb%91%e6%a0%91%e4%bb%80%e4%b9%88%e6%97%b6%e5%80%99%e4%bc%9a%e9%80%80%e5%8c%96%e6%88%90%e9%93%be%e8%a1%a8">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<p>主要有以下两种情况会退化成链表：</p>
<ul>
<li><strong>情况1:</strong> 在<strong>扩容时</strong>如果拆分了树，树元素个数＜=6则会退化链表。</li>
<li><strong>情况2:</strong> <strong>删除树节点时</strong>，若 <code>root</code>，<code>root.left</code>，<code>root.right</code>，<code>root.left.left</code> 中有任一个为null，也会退化为链表。</li>
</ul>
</div>
</label>
</div>
<h3 id="索引相关问题">
  索引相关问题
  <a class="anchor" href="#%e7%b4%a2%e5%bc%95%e7%9b%b8%e5%85%b3%e9%97%ae%e9%a2%98">#</a>
</h3>
<h4 id="索引计算方法">
  索引计算方法？
  <a class="anchor" href="#%e7%b4%a2%e5%bc%95%e8%ae%a1%e7%ae%97%e6%96%b9%e6%b3%95">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<ol>
<li>计算对象的 <code>hashCode()</code></li>
<li>调用 HashMap 的 <code>hash()</code>方法进行二次哈希</li>
<li><code>&amp; (capacity – 1)</code> 得到索引</li>
</ol>
</div>
</label>
</div>
<h4 id="hashcode-都有了为何还要提供-hash-方法">
<code>hashCode</code> 都有了，为何还要提供 <code>hash()</code> 方法？
  <a class="anchor" href="#hashcode-%e9%83%bd%e6%9c%89%e4%ba%86%e4%b8%ba%e4%bd%95%e8%bf%98%e8%a6%81%e6%8f%90%e4%be%9b-hash-%e6%96%b9%e6%b3%95">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
      二次 <code>hash()</code> 是为了综合高位数据，让哈希分布更为均匀。
    </div>
</label>
</div>
<h4 id="数组容量为何是-2-的-n-次幂">
  数组容量为何是 2 的 n 次幂？
  <a class="anchor" href="#%e6%95%b0%e7%bb%84%e5%ae%b9%e9%87%8f%e4%b8%ba%e4%bd%95%e6%98%af-2-%e7%9a%84-n-%e6%ac%a1%e5%b9%82">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<ol>
<li>计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模</li>
<li>扩容时重新计算索引效率更高： hash &amp; oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap</li>
</ol>
<p><strong>求模运算优化</strong>：</p>
<pre tabindex="0"><code>97 % 16 可以写成 97 &amp; （16 - 1）
97 % 64 可以写成 97 &amp; （64 - 1）
</code></pre><p>按位与运算比求模运算效率高。 求模类似于除法运算，所耗费的CPU时钟周期比较长。</p>
<p>前提：除数必须是 2 的 n 次方</p>
</div>
</label>
</div>
<h3 id="put-与-扩容-相关问题">
  put 与 扩容 相关问题
  <a class="anchor" href="#put-%e4%b8%8e-%e6%89%a9%e5%ae%b9-%e7%9b%b8%e5%85%b3%e9%97%ae%e9%a2%98">#</a>
</h3>
<h4 id="put-流程">
  put 流程？
  <a class="anchor" href="#put-%e6%b5%81%e7%a8%8b">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<ol>
<li>HashMap 是懒惰创建数组的，首次使用才创建数组</li>
<li>计算索引（桶下标）</li>
<li>如果桶下标还没人占用，创建 Node 占位返回</li>
<li>如果桶下标已经有人占用
<ol>
<li>已经是 TreeNode 走红黑树的添加或更新逻辑</li>
<li>是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，并且容量大于等于64，走树化逻辑</li>
</ol>
</li>
<li>返回前检查容量是否超过阈值，一旦超过进行扩容</li>
</ol>
<p><strong>1.7 与 1.8 的区别</strong></p>
<ol>
<li>链表插入节点时，1.7 是头插法，1.8 是尾插法</li>
<li>1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容</li>
<li>1.8 在扩容计算 Node 索引时，会优化</li>
</ol>
</div>
</label>
</div>
<h4 id="扩容加载因子为何默认是-075f-">
  扩容（加载）因子为何默认是 0.75f ？
  <a class="anchor" href="#%e6%89%a9%e5%ae%b9%e5%8a%a0%e8%bd%bd%e5%9b%a0%e5%ad%90%e4%b8%ba%e4%bd%95%e9%bb%98%e8%ae%a4%e6%98%af-075f-">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<ol>
<li>在空间占用与查询时间之间取得较好的权衡</li>
<li>大于这个值，空间节省了，但链表就会比较长影响性能</li>
<li>小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多</li>
</ol>
</div>
</label>
</div>
<h3 id="并发问题">
  并发问题
  <a class="anchor" href="#%e5%b9%b6%e5%8f%91%e9%97%ae%e9%a2%98">#</a>
</h3>
<h4 id="多线程下操作-hashmap-会有什么问题">
  多线程下操作 HashMap 会有什么问题？
  <a class="anchor" href="#%e5%a4%9a%e7%ba%bf%e7%a8%8b%e4%b8%8b%e6%93%8d%e4%bd%9c-hashmap-%e4%bc%9a%e6%9c%89%e4%bb%80%e4%b9%88%e9%97%ae%e9%a2%98">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<p>多线程下操作 HashMap 主要有以下问题：</p>
<ol>
<li>扩容死链（1.7）</li>
<li>数据错乱（1.7、1.8）</li>
</ol>
</div>
</label>
</div>
<h4 id="key-的设计要求-">
  key 的设计要求 ？
  <a class="anchor" href="#key-%e7%9a%84%e8%ae%be%e8%ae%a1%e8%a6%81%e6%b1%82-">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<ol>
<li>HashMap 的 key 可以为 null，但 Map 的其他实现则不然</li>
<li>作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的一定要是不可变值，如 String、int等</li>
<li>key 的 hashCode 应该有良好的散列性</li>
</ol>
<p>如果 key 可变，例如修改了 age 会导致再次查询时查询不到</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;" tabindex="0"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">HashMapMutableKey</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">main</span><span style="color:#f92672">(</span>String<span style="color:#f92672">[]</span> args<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        HashMap<span style="color:#f92672">&lt;</span>Student<span style="color:#f92672">,</span> Object<span style="color:#f92672">&gt;</span> map <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> HashMap<span style="color:#f92672">&lt;&gt;();</span>
</span></span><span style="display:flex;"><span>        Student stu <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> Student<span style="color:#f92672">(</span><span style="color:#e6db74">"张三"</span><span style="color:#f92672">,</span> <span style="color:#ae81ff">18</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>        map<span style="color:#f92672">.</span><span style="color:#a6e22e">put</span><span style="color:#f92672">(</span>stu<span style="color:#f92672">,</span> <span style="color:#66d9ef">new</span> Object<span style="color:#f92672">());</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        System<span style="color:#f92672">.</span><span style="color:#a6e22e">out</span><span style="color:#f92672">.</span><span style="color:#a6e22e">println</span><span style="color:#f92672">(</span>map<span style="color:#f92672">.</span><span style="color:#a6e22e">get</span><span style="color:#f92672">(</span>stu<span style="color:#f92672">));</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        stu<span style="color:#f92672">.</span><span style="color:#a6e22e">age</span> <span style="color:#f92672">=</span> <span style="color:#ae81ff">19</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        System<span style="color:#f92672">.</span><span style="color:#a6e22e">out</span><span style="color:#f92672">.</span><span style="color:#a6e22e">println</span><span style="color:#f92672">(</span>map<span style="color:#f92672">.</span><span style="color:#a6e22e">get</span><span style="color:#f92672">(</span>stu<span style="color:#f92672">));</span>  <span style="color:#75715e">// 查询为 空
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Student</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        String name<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">int</span> age<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">public</span> <span style="color:#a6e22e">Student</span><span style="color:#f92672">(</span>String name<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> age<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">this</span><span style="color:#f92672">.</span><span style="color:#a6e22e">name</span> <span style="color:#f92672">=</span> name<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">this</span><span style="color:#f92672">.</span><span style="color:#a6e22e">age</span> <span style="color:#f92672">=</span> age<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">public</span> String <span style="color:#a6e22e">getName</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">return</span> name<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">setName</span><span style="color:#f92672">(</span>String name<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">this</span><span style="color:#f92672">.</span><span style="color:#a6e22e">name</span> <span style="color:#f92672">=</span> name<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">getAge</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">return</span> age<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">setAge</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> age<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">this</span><span style="color:#f92672">.</span><span style="color:#a6e22e">age</span> <span style="color:#f92672">=</span> age<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        <span style="color:#a6e22e">@Override</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">boolean</span> <span style="color:#a6e22e">equals</span><span style="color:#f92672">(</span>Object o<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">this</span> <span style="color:#f92672">==</span> o<span style="color:#f92672">)</span> <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">true</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>o <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">||</span> getClass<span style="color:#f92672">()</span> <span style="color:#f92672">!=</span> o<span style="color:#f92672">.</span><span style="color:#a6e22e">getClass</span><span style="color:#f92672">())</span> <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            Student student <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>Student<span style="color:#f92672">)</span> o<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">return</span> age <span style="color:#f92672">==</span> student<span style="color:#f92672">.</span><span style="color:#a6e22e">age</span> <span style="color:#f92672">&amp;&amp;</span> Objects<span style="color:#f92672">.</span><span style="color:#a6e22e">equals</span><span style="color:#f92672">(</span>name<span style="color:#f92672">,</span> student<span style="color:#f92672">.</span><span style="color:#a6e22e">name</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>        <span style="color:#a6e22e">@Override</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">hashCode</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">return</span> Objects<span style="color:#f92672">.</span><span style="color:#a6e22e">hash</span><span style="color:#f92672">(</span>name<span style="color:#f92672">,</span> age<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div>
</div>
</label>
</div>
<h3 id="key-相关问题">
  key 相关问题
  <a class="anchor" href="#key-%e7%9b%b8%e5%85%b3%e9%97%ae%e9%a2%98">#</a>
</h3>
<h4 id="string-对象的-hashcode-设计">
  String 对象的 <code>hashCode()</code> 设计?
  <a class="anchor" href="#string-%e5%af%b9%e8%b1%a1%e7%9a%84-hashcode-%e8%ae%be%e8%ae%a1">#</a>
</h4>
<div class="book-expand">
<label>
<div class="book-expand-head flex justify-between">
<span>点击展开</span>
<span>...</span>
</div>
<input class="hidden" type="checkbox"/>
<div class="book-expand-content markdown-inner">
<ul>
<li>
<p>目标是达到较为均匀的散列效果，每个字符串的 hashCode 足够独特</p>
</li>
<li>
<p>字符串中的每个字符都可以表现为一个数字，称为</p>
</li>
</ul>
<link href="/katex/katex.min.css" rel="stylesheet"/>
<script defer="" src="/katex/katex.min.js"></script>
<script defer="" onload="renderMathInElement(document.body);" src="/katex/auto-render.min.js"></script><span>
  \( S_i \)
</span>
，其中 i 的范围是 0 ~ n - 1 
<ul>
<li>散列公式为：</li>
</ul>
<span>
  \[S_0∗31^{(n-1)}+ S_1∗31^{(n-2)}+ … S_i ∗ 31^{(n-1-i)}+ …S_{(n-1)}∗31^0\]
</span>
<ul>
<li>31 代入公式有较好的散列特性，并且 31 * h 可以被优化为</li>
</ul>
<span>
  \[32 ∗h -h\]
</span>
<p>等同于：</p>
<span>
  \[2^5  ∗h -h\]
</span>
<p>等同于：</p>
<span>
  \[h≪5  -h\]
</span>
</div>
</label>
</div>
</article>
<footer class="book-footer">
<div class="flex flex-wrap justify-between">
</div>
<script>(function(){function e(e){const t=window.getSelection(),n=document.createRange();n.selectNodeContents(e),t.removeAllRanges(),t.addRange(n)}document.querySelectorAll("pre code").forEach(t=>{t.addEventListener("click",function(){if(window.getSelection().toString())return;e(t.parentElement),navigator.clipboard&&navigator.clipboard.writeText(t.parentElement.textContent)})})})()</script>
</footer>
<div class="book-comments">
</div>
<label class="hidden book-menu-overlay" for="menu-control"></label>
</div>
<aside class="book-toc">
<div class="book-toc-content">
<nav id="TableOfContents">
<ul>
<li><a href="#hashmap-相关学习总结">HashMap 相关学习总结</a>
<ul>
<li><a href="#相关问题">相关问题</a>
<ul>
<li><a href="#红黑树相关问题">红黑树相关问题</a>
<ul>
<li><a href="#关于底层数据结构hashmap-的-jdk-17-和-jdk-18-有何不同">关于底层数据结构，HashMap 的 JDK 1.7 和 JDK 1.8 有何不同？</a></li>
<li><a href="#为什么要用红黑树">为什么要用红黑树？</a></li>
<li><a href="#为何不一上来就树化">为何不一上来就树化？</a></li>
<li><a href="#树化阈值为何为-8">树化阈值为何为 8？</a></li>
<li><a href="#是不是一超过阈值就立马变为红黑树是否要满足一些其他条件">是不是一超过阈值就立马变为红黑树？是否要满足一些其他条件？</a></li>
<li><a href="#红黑树什么时候会退化成链表">红黑树什么时候会退化成链表？</a></li>
</ul>
</li>
<li><a href="#索引相关问题">索引相关问题</a>
<ul>
<li><a href="#索引计算方法">索引计算方法？</a></li>
<li><a href="#hashcode-都有了为何还要提供-hash-方法"><code>hashCode</code> 都有了，为何还要提供 <code>hash()</code> 方法？</a></li>
<li><a href="#数组容量为何是-2-的-n-次幂">数组容量为何是 2 的 n 次幂？</a></li>
</ul>
</li>
<li><a href="#put-与-扩容-相关问题">put 与 扩容 相关问题</a>
<ul>
<li><a href="#put-流程">put 流程？</a></li>
<li><a href="#扩容加载因子为何默认是-075f-">扩容（加载）因子为何默认是 0.75f ？</a></li>
</ul>
</li>
<li><a href="#并发问题">并发问题</a>
<ul>
<li><a href="#多线程下操作-hashmap-会有什么问题">多线程下操作 HashMap 会有什么问题？</a></li>
<li><a href="#key-的设计要求-">key 的设计要求 ？</a></li>
</ul>
</li>
<li><a href="#key-相关问题">key 相关问题</a>
<ul>
<li><a href="#string-对象的-hashcode-设计">String 对象的 <code>hashCode()</code> 设计?</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</nav>
</div>
</aside>
</main>
</body>
</html>
